#include <bits/stdc++.h>
using namespace std;
struct ListNode
{
    ListNode *next;
    int val;
};
class Solution
{
  public:
    // 判断有没有环，返回相遇的地方
    ListNode *hasCycle(ListNode *head)
    {
        // 先判断链表为空的情况
        if (head == NULL)
            return NULL;
        // 快慢双指针
        ListNode *fast = head;
        ListNode *slow = head;
        // 如果没环快指针会先到链表尾
        while (fast != NULL && fast->next != NULL)
        {
            // 快指针移动两步
            fast = fast->next->next;
            // 慢指针移动一步
            slow = slow->next;
            // 相遇则有环
            if (fast == slow)
                // 返回相遇的地方
                return slow;
        }
        // 到末尾则没有环
        return NULL;
    }

    ListNode *EntryNodeOfLoop(ListNode *pHead)
    {
        ListNode *slow = hasCycle(pHead);
        // 没有环
        if (slow == NULL)
            return NULL;
        // 快指针回到表头
        ListNode *fast = pHead;
        // 再次相遇即是环入口
        while (fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution
{
  public:
    ListNode *EntryNodeOfLoop(ListNode *pHead)
    {
        ListNode *fast = pHead;
        ListNode *slow = pHead;

        // 检测是否有环
        bool flag = false;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
            {
                flag = true;
                break;
            }
        }
        if (!flag)
            return nullptr;
        // 返回第一个头
        slow = pHead;
        while (fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

// 为什么 fast 只走一步？
// 在第二阶段，快指针 fast 和慢指针 slow 需要以 相同的速度
// 移动，才能保证它们最终在环的入口节点相遇。这是因为：

// 设链表头到环入口的距离为 a，环入口到相遇点的距离为 b，环的长度为 c。

// 在第一阶段，快指针和慢指针相遇时，快指针比慢指针多走了 n 圈环的距离（n >=
// 1）。

// 通过数学推导可以证明，当 slow 从链表头开始，fast
// 从相遇点开始，两者以相同速度移动时，它们会在环的入口节点相遇。

// 因此，第二阶段 fast
// 只走一步是为了让快慢指针以相同的速度移动，从而找到环的入口